// https://leetcode.cn/problems/reverse-nodes-in-k-group/
/*
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
*/
#include <vector>
#include <iostream>

using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
		if(k == 1){
			return head;
		}
		ListNode * dummy = new ListNode(-1);
		dummy->next = head;
		ListNode * prev = dummy;
		
		
		int i = 1;
		ListNode * index = head; // 计数用
		ListNode * left = index;
		ListNode * right = nullptr;
		while(index){
			index = index->next;
			i++;
			if(i == k){
				right = index;
				if(!right){
					break;
				}
				// cout << "left:" << left->val << ",right:" << right->val << endl;
				ListNode * rightNext = right->next;
				
				reverse(left, right);
				
				// cout << "reversed left:" << left->val << ",right:" << right->val << endl;
				
				prev->next = right;
				// cout << "right:" << right->val<< ",right->next:" << right->next->val << endl;
				prev = left;
				left = rightNext;
				index = rightNext;
				i = 1; // i 清零
			}
		}
		return dummy->next;
    }
	
	void reverse(ListNode * head, ListNode * tail){
		ListNode * left = head;
		ListNode * mid = head->next;
		head->next = tail->next;
		
		while(mid != tail){
			ListNode * right = mid->next;
			mid->next = left;
			left = mid;
			mid = right;
		}
		
		mid->next = left;
		// cout << "in mid:" << mid->val << ",mid->next:" << mid->next->val << endl;
	}
	
	ListNode * init(){
		vector<int> init = {4, 3, 2, 1, 0, 5, 6};
		int len = init.size();
		
		ListNode * head = new ListNode(init[0]);
		ListNode * index = head;
		for(int i = 1; i < len; i++){
			ListNode * tmp = new ListNode(init[i]);
			index->next = tmp;
			index = index->next;
		}
		return head;
	}
	
	void show(ListNode * head){
		while(head){
			cout << head->val << ",";
			head = head->next;
		}
		cout <<endl;
	}
};

int main(){
	Solution so;
	ListNode * head = so.init();
	so.show(head);
	ListNode * h1 = so.reverseKGroup(head, 3);
	so.show(h1);
	return 0;
	
}